package org.leetcode.easy;

import org.junit.Test;
import org.leetcode.utils.ListNode;

import java.util.ArrayList;
import java.util.HashSet;

// 160. 相交链表
public class GetIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ArrayList<ListNode> list = new ArrayList<>();
        while (headA != null || headB != null) {
            if (headA != null) {
                if (!list.contains(headA)) {
                    list.add(headA);
                } else {
                    return headA;
                }
                headA = headA.next;
            }

            if (headB != null) {
                if (!list.contains(headB)) {
                    list.add(headB);
                } else {
                    return headB;
                }
                headB = headB.next;
            }
        }
        return null;
    }

    // 优化版
    public ListNode getIntersectionNodeBest(ListNode headA, ListNode headB) {
        HashSet<ListNode> seen = new HashSet<>();
        ListNode nodeA = headA;
        ListNode nodeB = headB;

        // 遍历第一个链表
        while (nodeA != null) {
            // 检查是否以前已经遇到过该节点
            if (seen.contains(nodeA)) {
                return nodeA; // 链表A和链表B相交于nodeA
            }
            seen.add(nodeA); // 将节点添加到集合中
            nodeA = nodeA.next;
        }

        // 重置指针并遍历第二个链表
        while (nodeB != null) {
            // 检查是否以前已经遇到过该节点
            if (seen.contains(nodeB)) {
                return nodeB; // 链表A和链表B相交于nodeB
            }
            nodeB = nodeB.next;
        }

        // 没有找到相交节点
        return null;
    }

    @Test
    public void test() {
        ListNode headA = new ListNode(3);
        ListNode headB = new ListNode(2);
        headB.next = headA;
        System.out.println(getIntersectionNode(headA, headB));
    }
}
